package doublePointer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;

public class threeSum {
    // 直接双指针
    // 有错误，没有完全遍历
    // public static List<List<Integer>> threeSum(int[] nums) {
    // //
    // // 首先增序排序
    // Arrays.sort(nums);
    // // 全正或者全负
    // if (nums[0] > 0 || nums[nums.length - 1] < 0) {
    // return Collections.emptyList();
    // }
    // int left = 0, mid = 1, right = nums.length - 1;
    // boolean leftFlag = true;
    // if (Math.abs(nums[left]) > nums[right]) {
    // mid = right - 1;
    // leftFlag = false;

    // } else if (Math.abs(nums[left]) < nums[right]) {
    // mid = left + 1;
    // } else {
    // mid = right - 1;
    // leftFlag = false;
    // }
    // // 两边相等的情况，要分两种情况讨论
    // // 确保剩余3个元素
    // List<List<Integer>> list = new ArrayList<>();

    // // if (left==mid||right==mid) {
    // // break;
    // // }
    // // 看哪边大，mid就从小的那边开始

    // // 移动mid
    // while (left < mid && mid < right) {
    // if (leftFlag) {
    // if (nums[left] + nums[mid] + nums[right] > 0) {
    // // right太大了
    // right--;
    // } else if (nums[left] + nums[mid] + nums[right] < 0) {
    // // mid太小
    // mid++;
    // }
    // } else {
    // if (nums[left] + nums[mid] + nums[right] > 0) {
    // // right太大了
    // mid--;
    // } else if (nums[left] + nums[mid] + nums[right] < 0) {
    // // left太小
    // left++;
    // }
    // }
    // if (left == mid || mid == right) {
    // break;
    // }
    // if (nums[left] + nums[mid] + nums[right] == 0) {
    // ArrayList<Integer> subList = new ArrayList<>();
    // // 排序
    // subList.add(nums[left]);
    // subList.add(nums[mid]);
    // subList.add(nums[right]);
    // subList.sort(new Comparator<Integer>() {
    // @Override
    // public int compare(Integer o1, Integer o2) {
    // // 返回int类型：o1 - o2 表示升序排序
    // return o1 - o2;
    // }
    // });
    // if (!list.contains(subList)) {
    // list.add(subList);
    // }
    // // 移动
    // // -3 -2 -1 0 1 2 3 4 5 6 7 8

    // if (leftFlag) {
    // right--;

    // } else {
    // left++;
    // }
    // if (Math.abs(nums[left]) > nums[right]) {
    // mid = right - 1;
    // leftFlag = false;

    // } else if (Math.abs(nums[left]) < nums[right]) {
    // mid = left + 1;
    // leftFlag = true;
    // } else {
    // // mid = right - 1;
    // // leftFlag = false;
    // mid = left + 1;
    // leftFlag = true;
    // }
    // // break;
    // }
    // }

    // return list.size() > 0 ? list : Collections.emptyList();
    // }
    public static List<List<Integer>> threeSum(int[] nums) {

        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<>();
        for (int left = 0; left < nums.length; left++) {
            if (left - 1 >= 0 && nums[left] == nums[left - 1]) {
                // 过滤掉重复的数字
                //每个都跟上一个不相同
                continue;
            }
            int mid = left + 1, right = nums.length - 1;
            while (mid < right) {
                if (mid  > left+1 && nums[mid] == nums[mid - 1]) {
                        //mid和mid-1对比时，要先取过一遍，因为他是和自己上一次做对比，因此mid  > left+1
                        //否则0 0 0 0
                        // 过滤掉重复的数字
                        mid++;
                        continue;
                    }
                if (nums[left] + nums[mid] + nums[right] == 0) {

                    ArrayList<Integer> subList = new ArrayList<>();
                    // 排序
                    subList.add(nums[left]);
                    subList.add(nums[mid]);
                    subList.add(nums[right]);
                    //不能使用list.contains来去重，因为是n^2的复杂度，会超时
                    // subList.sort(new Comparator<Integer>() {
                    // @Override
                    // public int compare(Integer o1, Integer o2) {
                    // // 返回int类型：o1 - o2 表示升序排序
                    // return o1 - o2;
                    // }
                    // });
                    // if (!list.contains(subList)) {
                    // list.add(subList);
                    // }
                    list.add(subList);
                    mid++;
                    // 过滤重复的数字
                    
                } else if (nums[left] + nums[mid] + nums[right] > 0) {
                    right--;
                } else {
                    mid++;
                }

            }

        }

        return list;
    }

    public static void main(String[] args) {
        // int[] nums = new int[] { -1, 0, 1, 2, -1, -4 };
        // int[] nums = new int[] { 3, 2, -1, -4 };
        // int[] nums = new int[] { 1,2, -1, -2 };
        // int[] nums = new int[] { 2, -3, 0, -2, -5, -5, -4, 1, 2, -2, 2, 0, 2, -4,
        // 5,5, -10 };
        int[] nums = new int[] { 0, 0, 0, 0 };
        List<List<Integer>> threeSum = threeSum(nums);
        for (List<Integer> subthreeSum : threeSum) {
            System.out.println("==========");
            for (Integer rs : subthreeSum) {
                System.out.println(rs);
            }
        }
    }
}
